#include <iostream>

using namespace std;

/*

*/
//时间1ms JAVA：
// class Solution {
//     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//         int tmp = 0;
//         ListNode result = new ListNode(-1);
//         ListNode pre = result;
//         //处理链表相同长度部分
//         while(l1!=null && l2!=null){
//             int num = l1.val + l2.val;
//             if(tmp > 0){
//                 num++;
//             }
//             ListNode tmpData = new ListNode(num%10);
//             tmp = num/10;
//             l1=l1.next;
//             l2=l2.next;
//             result.next = tmpData;
//             result = result.next;
//         }
//         //处理长链表剩余部分
//         if(l1!=null){
//             while(tmp>0 && l1!=null){
//                 int num = l1.val + 1;
//                 ListNode tmpData = new ListNode(num%10);
//                 tmp = num / 10;
//                 l1=l1.next;
//                 result.next = tmpData;
//                 result = result.next;
//             }
//             result.next = l1;
//         }else if(l2!=null){
//             while(tmp>0 && l2!=null){
//                 int num = l2.val + 1;
//                 ListNode tmpData = new ListNode(num%10);
//                 tmp = num / 10;
//                 l2=l2.next;
//                 result.next = tmpData;
//                 result = result.next;
//             }
//             result.next = l2;
//         }
//         if(tmp == 1){
//             ListNode tmpData = new ListNode(1);
//             result.next = tmpData;
//         }
//         return pre.next;
//     }
// }

// C语言 目前最优
struct ListNode
{
    int val;
    struct ListNode *next;
};

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    struct ListNode *ret = l1;
    uint8_t carry; ///< 进位标志

    ///  第一位相加，记录进位标志并保留个位
    if (carry = ((l1->val += l2->val) > 9))
    {
        l1->val -= 10;
    }

    while (l2->next) ///< 遍历l2
    {
        l2 = l2->next;
        if (l1->next)
        {
            l1 = l1->next;
            if (carry = ((l1->val += (l2->val + carry)) > 9))
            {
                l1->val -= 10;
            }
        }
        else ///< l1到末尾时
        {
            l1->next = l2; ///< 直接连接到l2当前结点
            while (carry)  ///< 判断是否有进位
            {
                if (carry = ((l2->val += carry) > 9))
                {
                    l2->val -= 10;
                    if (!l2->next)
                    {
                        l2->next = (struct ListNode *)malloc(sizeof(struct ListNode));
                        l2 = l2->next;
                        l2->next = NULL;
                        l2->val = 1;
                        carry = 0;
                        break;
                    }
                    else
                    {
                        l2 = l2->next;
                    }
                }
            }
            return ret;
        }
    }

    while (carry)
    {
        if (!l1->next)
        {
            l1->next = (struct ListNode *)malloc(sizeof(struct ListNode));
            l1->next->next = NULL;
            l1->next->val = 0;
        }
        l1 = l1->next;
        if (carry = ((l1->val += carry) > 9))
        {
            l1->val -= 10;
        }
    }

    return ret;
}

// 解法1：
// 整体思路：
// 将长度较短的链表在末尾补零使得两个连表长度相等，再一个一个元素对其相加（考虑进位）

// 1.获取两个链表所对应的长度
// 2.在较短的链表末尾补零
// 3.对齐相加考虑进位

// Definition for singly-linked list.
struct ListNode
{
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        int len1 = 1; //记录l1的长度
        int len2 = 1; //记录l2的长度
        ListNode *p = l1;
        ListNode *q = l2;
        while (p->next != NULL) //获取l1的长度
        {
            len1++;
            p = p->next;
        }
        while (q->next != NULL) //获取l2的长度
        {
            len2++;
            q = q->next;
        }
        if (len1 > len2) // l1较长，在l2末尾补零
        {
            for (int i = 1; i <= len1 - len2; i++)
            {
                q->next = new ListNode(0);
                q = q->next;
            }
        }
        else // l2较长，在l1末尾补零
        {
            for (int i = 1; i <= len2 - len1; i++)
            {
                p->next = new ListNode(0);
                p = p->next;
            }
        }
        p = l1;
        q = l2;
        bool count = false;              //记录进位
        ListNode *l3 = new ListNode(-1); //存放结果的链表
        ListNode *w = l3;                // l3的移动指针
        int i = 0;                       //记录相加结果
        while (p != NULL && q != NULL)
        {
            i = count + p->val + q->val;
            w->next = new ListNode(i % 10);
            count = i >= 10 ? true : false;
            w = w->next;
            p = p->next;
            q = q->next;
        }
        if (count) //若最后还有进位
        {
            w->next = new ListNode(1);
            w = w->next;
        }
        return l3->next;
    }
};

// 解法2：
// 整体思路：
// 不对齐补零，若链表不为空则用 sum(代表每个位的和的结果)加上，考虑进位。

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode(-1); //存放结果的链表
        ListNode *h = head;                //移动指针
        int sum = 0;                       //每个位的加和结果
        bool carry = false;                //进位标志
        while (l1 != NULL || l2 != NULL)
        {
            sum = 0;
            if (l1 != NULL)
            {
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL)
            {
                sum += l2->val;
                l2 = l2->next;
            }
            if (carry)
                sum++;
            h->next = new ListNode(sum % 10);
            h = h->next;
            carry = sum >= 10 ? true : false;
        }
        if (carry)
        {
            h->next = new ListNode(1);
        }
        return head->next;
    }
};
